package com.cat.dynamicPlanning;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/form-largest-integer-with-digits-that-add-up-to-target/
 * @create 2025/9/4 19:19
 * @since JDK17
 */

public class Solution69 {
    String max(String s1, String s2) {
        if (s1 == null) {
            return s2;
        }
        if (s1.length() > s2.length()) {
            return s1;
        } else if (s1.length() < s2.length()) {
            return s2;
        } else {
            if (s1.compareTo(s2) > 0) {
                return s1;
            } else {
                return s2;
            }
        }
    }

    public String largestNumber(int[] cost, int target) {
        // 完全背包 : 单个物品可以用多次
        // dp[j] : 使用j代价i件物品可以取得的最大值
        int n = cost.length;
        String[] dp = new String[target + 1];
        dp[0] = "";

        for (int i = 9; i > 0; i--) {
            for (int j = cost[i - 1]; j <= target; j++) {
                if (dp[j - cost[i - 1]] != null) {
                    dp[j] = max(dp[j], dp[j - cost[i - 1]] + String.valueOf(i));
                }
            }
        }
        return dp[target] == null ? "0" : dp[target];
    }
}
